package demo01Array;

import org.junit.Test;

/**
 * @ClassName $ {NAME}
 * @Description TODO
 * @Author shenxinyuan
 * @Date $ {DATE} $ {TIME}
 * @Version 1. 0
 **/

public class SmallestNumInRotateArray {

    private int [] arr = {3,4,5,1,2};

    /**
     * @Author shenxinyuan
     * @Description //TODO 时间复杂度：二分，所以为O(longN)， 但是如果是[1, 1, 1, 1],会退化到O(n)
     * 空间复杂度：没有开辟额外空间，为O(1)
     * @Date 13:46 2021/7/17
     * @Param [rotateArray]
     * @return int
     **/
    public int minNumberInRotateArray(int []rotateArray) {
        if (rotateArray.length == 0) return 0;

        int first = 0, last = rotateArray.length - 1;
        while (first < last) { // 最后剩下一个元素，即为答案
            if (rotateArray[first] < rotateArray[last]) { // 提前退出
                return rotateArray[first];
            }
            int mid = first + ((last - first) >> 1);

            if (rotateArray[mid] > rotateArray[last]) { // 情况1
                first = mid + 1;
            } else if (rotateArray[mid] < rotateArray[last]) { //情况2
                last = mid;
            } else { // 情况3
                --last;
            }
        }
        return rotateArray[first];
    }


    @Test
    public void test() {
        minNumberInRotateArray(arr);
    }
}
